By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 15, Issue 2, pp. 317-627

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Optimal Point Location in a Monotone Subdivision

Herbert Edelsbrunner, Leonidas J. Guibas, and Jorge Stolfi

pp. 317-340

BibTeX  Abstract Full Text:  PDF

Constructing Arrangements of Lines and Hyperplanes with Applications

H. Edelsbrunner, J. O'Rourke, and R. Seidel

pp. 341-363

BibTeX  Abstract Full Text:  PDF

A Simple Unpredictable Pseudo-Random Number Generator

L. Blum, M. Blum, and M. Shub

pp. 364-383

BibTeX  Abstract Full Text:  PDF

Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average

Lenore Blum and Michael Shub

pp. 384-398

BibTeX  Abstract Full Text:  PDF

Optimal Approximations and Polynomially Levelable Sets

Pekka Orponen, David A. Russo, and Uwe Schöning

pp. 399-408

BibTeX  Abstract Full Text:  PDF

Probabilistic Bounds on the Performance of List Scheduling

John L. Bruno and Peter J. Downey

pp. 409-417

BibTeX  Abstract Full Text:  PDF

Minimal Representation of Directed Hypergraphs

G. Ausiello, A. D'Atri, and D. Saccà

pp. 418-431

BibTeX  Abstract Full Text:  PDF

Representations and Parallel Computations for Rational Functions

Joachim von zur Gathen

pp. 432-452

BibTeX  Abstract Full Text:  PDF

On the Complexity of Nonconvex Covering

Wolfgang Maass

pp. 453-467

BibTeX  Abstract Full Text:  PDF

Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel

Dan E. Willard

pp. 468-477

BibTeX  Abstract Full Text:  PDF

Efficient Algorithms for Geometric Graph Search Problems

Hiroshi Imai and Takao Asano

pp. 478-494

BibTeX  Abstract Full Text:  PDF

Planar Multicommodity Fows, Maximum Matchings and Negative Cycles

Kazuhiko Matsumoto, Takao Nishizeki, and Nobuji Saito

pp. 495-510

BibTeX  Abstract Full Text:  PDF

Relativizations of Unambiguous and Random Polynomial Time Classes

John Geske and Joachim Grollmann

pp. 511-519

BibTeX  Abstract Full Text:  PDF

Probabilities Related to Father-Son Distances in Binary Search Trees

Carl E. Langenhop and William E. Wright

pp. 520-530

BibTeX  Abstract Full Text:  PDF

Negation is Powerless for Boolean Slice Functions

L. G. Valiant

pp. 531-535

BibTeX  Abstract Full Text:  PDF

On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

A. M. Frieze

pp. 536-539

BibTeX  Abstract Full Text:  PDF

Constant Time Generation of Free Trees

Robert Alan Wright, Bruce Richmond, Andrew Odlyzko, and Brendan D. McKay

pp. 540-548

BibTeX  Abstract Full Text:  PDF

Bounds for Width Two Branching Programs

Allan Borodin, Danny Dolev, Faith E. Fich, and Wolfgang Paul

pp. 549-560

BibTeX  Abstract Full Text:  PDF

On the Probable Performance of Heuristics for Bandwidth Minimization

Jonathan S. Turner

pp. 561-580

BibTeX  Abstract Full Text:  PDF

The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals

Dung T. Huynh

pp. 581-594

BibTeX  Abstract Full Text:  PDF

Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix Multiplication

Rodney W. Johnson and Aileen M. McLoughlin

pp. 595-603

BibTeX  Abstract Full Text:  PDF

Collections of Functions for Perfect Hashing

Francine Berman, Mary Ellen Bock, Eric Dittert, Michael J. O'Donnell, and Darrell Plank

pp. 604-618

BibTeX  Abstract Full Text:  PDF

Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism

Joan Feigenbaum and Alejandro A. Schäffer

pp. 619-627

BibTeX  Abstract Full Text:  PDF